//下面这部件程序可以：
//(1)输入到头文件中，其文件名为 SLinkList.h，
//(2)也可以直接输入到主函数文件中，应在main函数前面。
#include <stdio.h> 
#include <stdlib.h>
#include <cstdlib>
//预定义常量和类型
# define TRUE   1
# define FALSE  0
# define OK     1
# define ERROR  0
# define OVERFLOWE  -2
//定义元素ElemType的类型
typedef int ElemType;   
//定义函数类型，其值是函数结果状态代码
typedef int Status;

//---- 单链表的存储结构-----P30
typedef struct LNode
{
	ElemType  data;        //结点的数据域
	struct LNode *next;    //结点的指针域
}LNode, *LinkList;   //LinkList为指向结构体 LNode 的指针类型

//---- 单链表的初始化 -----P32  算法2.6 
Status Init_LinkList(LinkList &L)
{  //构造一个空的单链表L
	L=new LNode;  //生成新结点为表头，表头指针L指向头结点
    L->next=NULL; //头结点的指针域置空
    return  OK;
}//Init_LinkList

//----建立有n个元素的单链表算法（前插法）----P36算法2.11有改动 
Status Create_LinkList(LinkList &L,ElemType a[],int n)
{  LinkList p;    
   //L=new LNode;          //L=(LinkList)malloc(sizeof(LNode));
   //L->next=NULL;         //先建立一个带头结点的空的单链表
  for (int i=n;i>0;--i)       //逆序输入
  {   p=new LNode;    //生成新结点p=(LinkList)malloc(sizeof(LNode)); 
      p->data=a[i-1];    //输入元素值
      p->next = L->next;
      L->next=p;    //结点指针指向表头结点（先挂上）
        //插入到表头
   }
   return OK;
}//Create_LinkList

//---- 遍历单链表 ----
Status Traverse_LinkList(LinkList L)
{   LinkList p;
    p=L->next;           //p指向第一个结点
    if(!p)  
   {	printf("表不存在\n");return 0;	}
    while(p)
    {   //遍历单链表
        printf("%d  ",p->data);  //输出结点的值
        p=p->next; //指针指向下一个结点 
    } 
    printf("\n"); 
    return OK;
 }// Traverse_LinkList

//---- 插入算法 ----
Status ListInsert_L(LinkList &L,int i,ElemType e)
{ //在带表头结点的单链表L中第i个位置之前插入元素e
  LinkList p,q;
  p=L; //可能要插入成为第一个元素,p为头指针
  int j=0;
  while(p && j<i-1)
  {  p=p->next;   //寻找第i-1个结点
     ++j;              //计数器加1
  }           
  if(!p|| j>i-1)return ERROR;   //i小于1或大于表长
  q=new LNode;     //生成新的结点q q=(LinkList)malloc(sizeof(Lnode))；
  q->data = e;      //q结点数据域赋值
  q->next = p->next; //q先连上
  p->next = q;       //p结点指向q
  return OK;
}//ListInsert_L

//---- 删除算法 ----
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{ //在带头结点的单链表L中删除第i个元素,并由e返回其值。
  LinkList q,p=L;int j=0;             //可能删除第一个结点
  while(p->next && j<i-1)                 
  {  p=p->next;++j; }    //寻找第i个结点，并令p指向其前驱
  if(!(p->next)|| j>i-1)   // 这个条件请认真记一下
     return ERROR;      //i小于1或大于表长
    q=p->next;            //指向被删除的结点
    e=q->data;            //获取被删除结点的值
    p->next = q->next;      //从L中删除q，q为第i个元素   
    free(q);            //释放结点 
  return OK;
}//ListDelete_L

//---- 按序号查找元素算法 ----
Status GetElem_L(LinkList L,int i,ElemType &e)  
{ //L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
  LinkList p=L->next; int j=1;    //初始化，p指向第一个结点，j为计数器
  while(p && j<i)  // 这个条件请认真记一下
  { //顺指针向后查找，直到p指向第i个元素或p为空。
       p=p->next; //p指针向后移动
       ++j;		  //计数器加1
  }
  if (!p|| j>i)return ERROR;        //第i个元素不存在
       e = p->data;           //取第i个元素
  return OK;	
}//GetElem_L

//---- 按值查找元素算法 ----
int Locate_L(LinkList L,ElemType x)
{ //L为带头结点的单链表的头指针。当线性表中存在值和x 相等的元素时，返回其位序，否则返回0。
  LinkList p=L->next;int i=1;      //初始化，p指向第一个结点，i为计数器
  while(p && p->data != x)
  { //顺指针向后查找，直到找到值和x相等的元素或p为空。
        p=p->next;  ++i;
  }
  if(!p) return 0;    //未找到
  return i;           //返回该元素的位序
}//Locate_L

//---- 计算单链表长度算法 ----
int Length( LinkList L ) 
{   int count = 0; 
    LinkList p = L->next;     //指针 p 指示第一个结点	
    while ( p != NULL ) 
    {  //逐个结点检测
         p=p->next;  
         count++;
    }			
    return count;
}

//---- 销毁单链表 ----
Status Destroy_LinkList(LinkList &L)
{    LinkList p;
     while(L) 
     {   
          p=L;
          L=L->next;
          delete p;
     }
     return OK; 
}// Destroy_LinkList

//---- 邓文华 P33 算法2.16 单链表的倒置算法
void reverse(LinkList H)
{  LNode *p,*q;
   p=H->next;
   H->next=NULL;
   while(p)
   {
          q=p;p=p->next;
          q->next=H->next;
          H->next=q;
   }
}


//下面这部分程序应输入到主函数文件中
#include <stdio.h>
#include <stdlib.h>
//#include <iostream>
//#include "SLinkList.h"  //如果前述应输入到头文件SLinkList.h中的代码是直接输入到主函数文件中，则这句应被注释
int main()
{
    LinkList L;
    int i,key=1,n;
	ElemType a[100]={2,3,2,3,0,8,1,0,0,4,7}; //这部分信息要个性化
	n=11;                 //元素个数应根据个性化信息的长度而定
    ElemType e;
	printf("============= 实验2 链表操作 =============\n ");
	printf(" 计算机科学与技术专升本3  23230810047  李皓天\n ");              //请填写相应的个人信息
	printf(" 测试数据：按要求构成\n ");     //请填写具体测试数据
    printf("=========== 实验报告 2023-11-07==========\n\n");   //这部分信息应与实验日期对应
	//调用初始化单链表函数
    int m=Init_LinkList(L);   
    printf(" 调用初始化单链表函数，返回值为: %d\n",m);

	//调用创建有n个元素的单链表函数
	m=Create_LinkList(L,a,n);	
	printf(" 调用创建有n个元素的单链表函数，返回值为: %d\n ",m);

	//调用遍历单链表函数，输出刚创建的有n个元素的单链表
	Traverse_LinkList(L); 
	
	printf(" 请输入插入元素的位置i及元素值,请用空格间隔\n ");
	scanf("%d%d",&i,&e);
	//调用在单链表中插入元素的函数，插入元素
	//Status ListInsert_L(LinkList &L，int i，ElemType e)
	ListInsert_L(L,i,e);
	//调用遍历单链表函数，输出插入元素后的单链表
	Traverse_LinkList(L);
	
	printf(" 请输入要删除元素的位置 i= ");
	scanf("%d",&i);
	//调用在单链表中删除元素的函数，删除元素
	//Status ListDelete_L(LinkList &L,int i,ElemType &e)
	ListDelete_L(L,i,e);
    printf(" 被删除的第%d个元素的值为%d\n ",i,e);
	//调用遍历单链表函数，输出删除元素后的单链表
	Traverse_LinkList(L);
	
	printf(" 请输入要查找元素的位置i= ");
	scanf("%d",&i);
	//调用在单链表按序号查找元素的函数
    //Status GetElem_L(LinkList L,int i,ElemType &e)
	if (GetElem_L(L,i,e))
		printf(" 第%d个元素的值为%d\n ",i,e);
	else 
		printf(" 第%d个元素不存在!\n ",i);

	printf(" 请输入要查找元素e的值: ");
	scanf("%d",&e);
	//调用在单链表按值查找元素算法(函数)
    //int Locate_L(LinkList L,ElemType x)
	i=Locate_L(L,e);
	printf(" 值为%d元素的位序为%d\n ",e,i);
	//printf("值为%d元素的位序为%d\n",e,Locate_L(L,e));

	//调用计算单链表长度算法(函数)
	//int Length( LinkList L )
	printf(" 单链表L的长度: %d\n ",Length(L));

	//调用单链表L的倒置算法
	printf(" 单链表L的倒置 \n");
    reverse(L);
	Traverse_LinkList(L);

    printf(" 按任意键销毁单链表L\n"); getchar();
	//调用销毁单链算法(函数)
	//Status Destroy_LinkList(LinkList &L)
	Destroy_LinkList(L);
    return 1;
}
